Key to CSE142 Final, Spring 2012         

1.      Original List                          Final list
        ----------------------------------------------- 
        {1, 0, 4, 2}                           {10, 6, 4, 2} 
        {17, 12, 8, 1, 4}                      {11, 6, 5, 1, 4}
        {23, 5, 14, 6, 2}                      {22, 14, 8, 6, 2}
        {17, 19, 7, 4, 1, 1}                   {8, 5, 3, 2, 1, 1}
        
2. Reference Mystery.  The program produces the following output:

        [w:20 h:40] 2 40
        [w:20 h:40] 2 10
        [w:60 h:10] 3 10
        [w:60 h:10] 2 3

3. Inheritance Mystery.  The program produces the following output:    

        Diamond
        Ruby 1
        Emerald 2

        Emerald
        Ruby 1
        Emerald 2

        Emerald
        Emerald 1
        Emerald 2

        Garnet
        Garnet 1
        Emerald 2

4. Token-based processing 

        public static double lowestPrice(Scanner s) {
            String name = s.next();
            double price = s.nextDouble();
            double lowest = price;
    
            while(s.hasNext()) {
                String sign = s.next();
                double amt = s.nextDouble();
                if (sign.equals("+")) {
                    price += amt;
                } else {
                    price -= amt;
                }
        
                if (price < lowest) {
                    lowest = price;
                }
            }
    
            System.out.println("Lowest " + name + " price today: $" + lowest);
            return lowest;
        }

5. Line-based processing

        public static boolean hasAlternatingParity(Scanner s) {
            String l1 = "";
            if (s.hasNextLine()) {
                l1 = s.nextLine();
            }

            while (s.hasNextLine()) {
                String l2 = s.nextLine();
        
                if (l1.length() % 2 == l2.length() % 2) {
                    return false;
                }
        
                l1 = l2;
            }
            return true;
        }

        public static boolean hasAlternatingParity(Scanner s) {
            int parity = 0;
            if (s.hasNextLine()) {
                String line = s.nextLine();
                parity = line.length() % 2;
            }
    
            while (s.hasNextLine()) {
                String line = s.nextLine(); 
                if (line.length() % 2 == parity) {
                    return false;
                }
                parity = line.length() % 2;
            }
            return true;
        }  

6. Array programming

        public static int[] insertMiddle(int[] a, int[] b) {
            int[] result = new int[a.length + b.length];
            for (int i = 0; i < a.length / 2; i++) {
                result[i] = a[i];
            }
    
            for (int i = 0; i < b.length; i++) {
                result[i + a.length / 2] = b[i];
            }
    
            for (int i = a.length / 2; i < a.length; i++) {
                result [i + b.length] = a[i];
            }

            /* Also okay:
             *
             * for (int i = 0; i < a.length / 2 + (a.length % 2); i++)
             *     result[i + ((a.length / 2) + b.length)] = a[i + (a.length / 2)];
             */

            return result;
        }

        public static int[] insertMiddle(int[] a, int[] b) {
            int lengthA = a.length;
            int lengthB = b.length;
            int[] result = new int[lengthA + lengthB];
            for (int i = 0; i < result.length; i++) {
                if (i < lengthA / 2)
                    result[i] = a[i];
                else if (i < (lengthA / 2 + lengthB))
                    result[i] = b[i - lengthA / 2];
                else
                    result[i] = a[i - lengthB];
            }
            return result;
        }

        public static int[] insertMiddle(int[] a, int[] b) {
            int[] c = new int[a.length + b.length];
            int n = 0;
    
            for (int i = 0; i < a.length / 2; i++) {
                c[n] = a[i];
                n++;
            }
    
            for (int i = 0; i < b.length; i++) {
                c[n] = b[i];
                n++;
            }
    
            for (int i = a.length / 2; i < a.length; i++) {
                c[n] = a[i];
                n++;
            }
            return c;
        }              
 
7. Critters

        public class JellyFish extends Critter {
            private int drift;
            private int moveCount;
            private int driftCount;
            private String display;
    
            public JellyFish() {
                Random r = new Random();
                drift = r.nextInt(9) + 1;
                display = "D";
            }
    
            public int getDrift() {
                return drift;
            }
    
            public boolean eat() {
                driftCount = drift;
                display = "D";
                return true;
            }
    
            public Direction getMove() {
                if (driftCount != 0) {
                    driftCount--;
                    return Direction.WEST;
                }
                Direction result;
                if (moveCount % 3 == 0) {
                    result = Direction.NORTH;
                    display = "D";
                } else {
                    result = Direction.CENTER;
                    display = "o";
                }
                moveCount++;
                return result;
            }
    
            public String toString() {
                return display;
            }    
        } 
        
8. Array programming

        public static void limitRuns(int[] nums, int n) {
             int count = 1;
            for (int i = nums.length - 1; i > 0; i--) {
                if (nums[i] == nums[i - 1]) {
                    count++;
                    if (count > n) {
                        for (int j = i; j < nums.length - 1; j++) {
                            nums[j] = nums[j + 1];
                        }
                        nums[nums.length - 1] = 0;
                    }
                } else {
                    count = 1;
                }
            }
        }

        public static void limitRuns(int[] nums, int n) {
            int tot = 0;
            int count = 1;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] == nums[i - 1]) {
                    count++;
                } else {
                    if (count > n) {
                        int amt = count - n;
                        tot += amt;
                        for (int j = i; j < nums.length; j++) {
                            nums[j - amt] = nums[j];
                        }
                        i -= amt;     // IMPORTANT
                    }
                    count = 1;
                }
            }
            for (int i = nums.length - tot; i < nums.length; i++) {
                nums[i] = 0;
            }
        }

        // need to be careful not to be stuck in infinite loop with 0s at end!
        public static void limitRuns(int[] nums, int n) {
            int count = 1;
            int tot = 1;
            for (int i = 1; i < nums.length - tot; i++) {
                if (nums[i] == nums[i - 1]) {
                    count++;
                    if (count > n) {
                        for (int j = i; j < nums.length - tot; j++) {
                            nums[j] = nums[j + 1];
                        }
                        nums[nums.length - tot] = 0;
                        tot++;
                        i--;
                    }
                } else {
                    count = 1;
                }
            }
        }

        public static void limitRuns(int[] nums, int n) {
            int nonReps = 1;
            int count = 1;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] == nums[i - 1]) {
                    count++;
                }

                if (nums[i] != nums[i - 1]) {
                    count = 1;
                }

                if (nums[i] != nums[i - 1] || count <= n) {
                    nums[nonReps] = nums[i];
                    nonReps++;
                } 
            }

            for (int i = nonReps; i < nums.length; i++) {
                nums[i] = 0;
            }
        }